package Hot100;

import common.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author zhangmin
 * @create 2021-12-30 18:16
 *
 * 打家劫舍系列：
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，给定一个代表每个房屋存放金额的非负整数数组，
 * 计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 * 198. 打家劫舍--两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
 * 213. 打家劫舍 II--所有的房屋都 围成一圈 ，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
 * 337. 打家劫舍 III--这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
 *
 */
public class rob198 {

    /**
     * 198. 打家劫舍
     * 是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
     * 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下
     * ，一夜之内能够偷窃到的最高金额。
     * dp[i]表示从第i间房屋开始抢，最多可以抢到的钱
     * dp[i]=Math.max(dp[i+1],dp[i+2]+nums[i])
     * */

    public int rob1(int[] nums) {
        int n=nums.length;
        int[] dp=new int[n+2];
        for (int i = n-1; i >= 0; i--) {
            dp[i]=Math.max(dp[i+1],nums[i]+dp[i+2]);
        }
        return dp[0];
    }

    /**
     * 213. 打家劫舍 II
     * 你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
     * 同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
     * 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
     * 对于首尾的房子有三种情况：1、两个都不抢  2、第一个抢，最后一个不抢  3、第一个不抢，最后一个抢
     * 只需要比较2,3即可，这两个选择最终的选择余地比1大，做最优的选择
     * */
    public int rob2(int[] nums) {
        int n=nums.length;
        if (n==1) return nums[0];
        return Math.max(robRange(nums,0,n-2),robRange(nums,1,n-1));
    }
    int robRange(int[] nums,int start,int end){
        int n=nums.length;
        int[] dp=new int[n+2];
        for (int i = end; i >= start; i--) {
            dp[i]=Math.max(dp[i+1],nums[i]+dp[i+2]);
        }
        return dp[start];
    }

    /**
     * 337. 打家劫舍 III
     * 在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。
     * 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
     * 如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。
     * dp+备忘录
     * */
    Map<TreeNode,Integer> memo=new HashMap<>();
    public int rob1(TreeNode root) {
        if (root==null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        //1、抢，然后去下下家
        int do_it=root.val+(root.left==null?0:rob1(root.left.left)+rob1(root.left.right))
                +(root.right==null?0:rob1(root.right.left)+rob1(root.right.right));
        int notdo=rob1(root.left)+rob1(root.right);
        int res=Math.max(do_it,notdo);
        memo.put(root,res);
        return res;
    }

    public int rob(TreeNode root) {
        int[] res=dp(root);
        return Math.max(res[0],res[1]);
    }
    /* 返回一个大小为 2 的数组 arr
    arr[0] 表示不抢 root 的话，得到的最大钱数
    arr[1] 表示抢 root 的话，得到的最大钱数 */
    int[] dp(TreeNode root){
        if (root==null)return new int[]{0,0};
        int[] left=dp(root.left);
        int[] right=dp(root.right);
        int do_it=root.val+left[0]+right[0];
        int notdo=Math.max(left[0],left[1])+Math.max(right[0],right[1]);
        return new int[]{notdo,do_it};

    }

}
